The present invention generally relates to a method for decoding convolutional codes and, more specifically, to a system and method for decoding convolutional error correcting codes using a maximum-likelihood decoding algorithm.
Error correcting codes are well known. Early codes included parity codes and block codes where syndromes are generated to help determine whether the received data stream at a receiving device is the same as the data stream that was sent by a transmitting device. Parity codes operate at the byte or word level while block codes operated on relatively large (typically, up to a couple of hundred bytes) message blocks. Recently, convolutional codes have enjoyed increasing popularity in both magnetic recording applications and communication systems, such as optical, wireline and wireless communication systems. In contrast to block codes, convolutional codes operate on serial data, one or a few bits at a time. The Viterbi algorithm is a widely used convolutional code decoding algorithm and is of the type known as a maximum-likelihood decoding algorithm.
In a typical system requiring forward error correction, the transmitting device uses an encoder to encode a stream of data before transmission through the channel in accordance with certain key parameters. Specifically, a constraint length (denoted as ‘k’), a code rate (denoted as r=‘number in’ divided by ‘number out’) and generator polynomials (denoted g0, g1, . . . g(#out−1) are defined and implemented by the encoder to encode the data stream. The encoded data stream also includes inserted redundant symbols that are generated based on the data stream. Convolutional encoders are well known in the art.
The convolutional encoder employs an algorithmic method to generate an encoded output stream that is based on the current input and a selected number of previous inputs to the encoder. The convolutional encoder may be described using a code tree with each digital input specifying a branch on the tree. In the tree view, each symbol (zero or one) drives the encoder to a different state.
After transmission of the encoded data stream to the receiving device, a decoder process operates on the encoded data stream to recover the original data stream from the encoded data stream. The decoder determines the original inputs to the encoder by exploiting the trellis structure of the code to determine the maximum likelihood path through the tree given the received sequence. More specifically, based upon the encoded input data, the constraint length (k) and the generator polynomials, a cost or path metric is computed for each possible branch of the tree diagram for the given decoder sample. The path-metric is the cost of traversing the tree to the current point. The computed branch-metric is then added to an accumulated path metric. The lower cost updated path for a given state is selected and stored as a selection bit. This selection bit is used by path-metric comparison logic to specify which of the two possible paths is more likely.
For each input sample, the cost at each node of the tree is computed and the lower cost path is chosen as a survivor. The selection bit for each of the nodes is stored in the survivor memory at a specific location based upon which node was being computed. By storing the selection bits in the survivor memory, a history of the most likely transitions into every given state for each input sample is retained. Once enough data is stored in the survivor memory, the output stage is activated. Although there are a number of different methods to recover the data stream from the survivor data. One of the most common techniques used for the recovery is the trace-back method. In the trace-back method, the stored survivor data corresponds to the tree connections computed by the decoder. Starting from the latest data point, the path through the code tree is reconstructed in reverse order so that the last bit out of trace-back corresponds to the very first data bit input to the encoder. Due to inherent properties of the convolutional code, the survivor data eventually merges to the maximum likelihood sequence of inputs. The number of samples required for this merging is called the convergence interval of the decoder. The traced back sequence after the convergence interval is the time reversed input sequence.
The trace-back process requires a large number of computations. These computations require many clock cycles and can result in stalls, delays, dropouts or interruption in delivering the received data stream to the user. Further, the trace-back process may be delayed by the hardware used to implement the Viterbi decode process because of setup and hold time requirements and computational overhead, such as the time to complete a double word memory access. Clearly, what is needed is an efficient trace-back process that minimizes the occurrence of delays, dropouts or interruptions.
To achieve high throughput rates in spite of the above described technical limitations, the current literature describes the use of a “fully unrolled and pipelined architecture.” See, for example, Engline Yeo et al., A 500-Mb/s Soft-Output Viterbi Decoder, IEEE Journal of Solid-State Circuits, Vol. 38, No. 7, July 2003. However, as reported in this article, the complexity, power consumption and circuit area are all increased when a pipelined architecture is used.
Moreover, the insertion of pipeline stages along the survivor selection path requires careful management of the next survivor bit selection logic. If the survivor memory used is actually 2(k−1)+1 bits wide then it is sufficient to pipeline adjust the multiplexor selector signal so that it lines up with the appropriate data word. However, in the case where the survivor bits are distributed across multiple memory words, the memory read address must also be adjusted to account for the data pipeline. Like the selector, the read address may be delayed to equalize the pipeline skew. Delaying the memory read address results in lowered performance of the trace-back phase reducing the output rate.
Another classical approach to the problem of pipeline skew and system stalls suggests that “[d]ue to the non-causality of this method, the memory trace-back method faces imminent pipeline stalls.” See E. Yeo, et al., Implementation of High Throughput Soft Output Viterbi Decoders, Proc. IEEE Workshop on Signal Processing Systems, pp. 146-151, San Diego, Calif., Oct. 16-18, 2002. Obviously, system stalling will have adverse effects on the system throughput.
What is needed is a system and method for implementing a pipelined architecture that substantially eliminates the possibility of stalls or delays without increasing power consumption or circuit area and that does not increase the complexity of the trace-back process.